package com.cat.graphTheory;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 *   @description https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/
 *   @author 曲大人的喵
 *   @create 2025/9/22 20:32
 *   @since JDK17
 */

public class Solution20 {
    public int minimumObstacles(int[][] grid) {
        int[] d = new int[]{-1, 0, 1, 0, -1};
        int n = grid.length, m = grid[0].length;
        int[][] dis = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.addFirst(new int[]{0, 0});
        dis[0][0] = 0;
        while (!q.isEmpty()) {
            var x = q.pollFirst();
            for (int i = 0; i < 4; i++) {
                int nx = x[0] + d[i], ny = x[1] + d[i + 1];
                if (nx == -1 || nx == n || ny == -1 || ny == m || dis[nx][ny] <= dis[x[0]][x[1]] + grid[nx][ny]) {
                    continue;
                }
                if (grid[nx][ny] == 1) {
                    q.addLast(new int[]{nx, ny});
                } else {
                    q.addFirst(new int[]{nx, ny});
                }
                dis[nx][ny] = dis[x[0]][x[1]] + grid[nx][ny];
            }
        }

        return dis[n - 1][m - 1];
    }
}
